Search results for "metric tree"
showing 7 items of 7 documents
Nearly tight bounds on the learnability of evolution
2002
Evolution is often modeled as a stochastic process which modifies DNA. One of the most popular and successful such processes are the Cavender-Farris (CF) trees, which are represented as edge weighted trees. The Phylogeny Construction Problem is that of, given /spl kappa/ samples drawn from a CF tree, output a CF tree which is close to the original. Each CF tree naturally defines a random variable, and the gold standard for reconstructing such trees is the maximum likelihood estimator of this variable. This approach is notoriously computationally expensive. We show that a very simple algorithm, which is a variant on one of the most popular algorithms used by practitioners, converges on the t…
A distance metric on binary trees using lattice-theoretic measures
1990
A so called height function which is a strictly antitone supervaluation is defined on binary trees. Via lattice-theoretic results and using the height function, we can define a distance metric on binary trees of size n which can be computed in expected time O(n 3/2 )
Space of signatures as inverse limits of Carnot groups
2021
We formalize the notion of limit of an inverse system of metric spaces with 1-Lipschitz projections having unbounded fibers. The construction is applied to the sequence of free Carnot groups of fixed rank n and increasing step. In this case, the limit space is in correspondence with the space of signatures of rectifiable paths in ℝn, as introduced by Chen. Hambly-Lyons’s result on the uniqueness of signature implies that this space is a geodesic metric tree. As a particular consequence we deduce that every path in ℝn can be approximated by projections of some geodesics in some Carnot group of rank n, giving an evidence that the complexity of sub-Riemannian geodesics increases with the step.…
Space of signatures as inverse limits of Carnot groups
2021
We formalize the notion of limit of an inverse system of metric spaces with 1-Lipschitz projections having unbounded fibers. The construction is applied to the sequence of free Carnot groups of fixed rank n and increasing step. In this case, the limit space is in correspondence with the space of signatures of rectifiable paths in ℝn, as introduced by Chen. Hambly-Lyons’s result on the uniqueness of signature implies that this space is a geodesic metric tree. As a particular consequence we deduce that every path in ℝn can be approximated by projections of some geodesics in some Carnot group of rank n, giving an evidence that the complexity of sub-Riemannian geodesics increases with the step.
Metric or partial metric spaces endowed with a finite number of graphs: a tool to obtain fixed point results
2014
Abstract We give some fixed point theorems in the setting of metric spaces or partial metric spaces endowed with a finite number of graphs. The presented results extend and improve several well-known results in the literature. In particular, we discuss a Caristi type fixed point theorem in the setting of partial metric spaces, which has a close relation to Ekelandʼs principle.
On the low-dimensional Steiner minimum tree problem in Hamming metric
2013
While it is known that the d-dimensional Steiner minimum tree problem in Hamming metric is NP-complete if d is part of the input, it is an open question whether this also holds for fixed dimensions. In this paper, this question is answered by showing that the Steiner minimum tree problem in Hamming metric is already NP-complete in 3 dimensions. Furthermore, we show that, the minimum spanning tree gives a 2-2d approximation on the Steiner minimum tree for d>=2. Using this result, we analyse the so-called k-LCA and A"k approximation algorithms and show improved approximation guarantees for low dimensions.
Generation of Valid Labeled Binary Trees
2003
International audience; Generating binary trees is a well-known problem. In this paper, we add some constraints to leaves of these trees. Such trees are used in the morphing of polygons, where a polygon P is represented by a binary tree T and each angle of P is a weight on a leaf of T. In the following, we give two algorithms to generate all binary trees, without repetitions, having the same weight distribution to their leaves and representing all parallel polygons to P.